<!DOCTYPE html>
<html lang="en">
  <head>
    <meta charset="UTF-8" />
    <meta name="viewport" content="width=device-width, initial-scale=1.0" />
    <title>hash</title>
  </head>
  <body>
    <script>
      class HashTable {
        constructor(limit) {
          this.storage = [];
          this.count = 0;
          this.limit = limit;
        }
        // 哈希函数
        hashFunc(str, size) {
          let hashCode = 0;
          for (let i = 0; i < str.length; i++) {
            hashCode = 37 * hashCode + str.charCodeAt(i);
          }
          let index = hashCode % size;
          return index;
        }
        // 插入修改
        put(key, value) {
          let index = this.hashFunc(key, this.limit),
            bucket = this.storage[index];
          if (bucket == null) {
            bucket = [];
            this.storage[index] = bucket;
          }
          // 修改
          for (let i = 0; i < bucket.length; i++) {
            let tuple = bucket[i];
            if (tuple[0] === key) {
              tuple[1] = value;
              return;
            }
          }
          // 添加
          bucket.push([key, value]);
          this.count += 1;
          // 判断是否需要扩容
          if (this.count >= this.limit * 0.75) {
            console.log(this.count);
            this.reSize(this.limit * 2);
          }
        }
        // 获取
        get(key) {
          let index = this.hashFunc(key, this.limit),
            bucket = this.storage[index];
          if (bucket == null) {
            return null;
          }
          for (let i = 0; i < bucket.length; i++) {
            let tuple = bucket[i];
            if (tuple[0] === key) {
              return tuple[1];
            }
          }
          return null;
        }
        // 删除
        remove(key) {
          let index = this.hashFunc(key, this.limit),
            bucket = this.storage[index];
          if (bucket == null) {
            return null;
          }
          for (let i = 0; i < bucket.length; i++) {
            let tuple = bucket[i];
            if (tuple[0] === key) {
              bucket.splice(i, 1);
              this.count--;
              if (this.count <= this.limit * 0.25) {
                this.reSize(Math.floor(this.limit / 2));
              }
              return tuple[1];
            }
          }
          return null;
        }
        isEmpty() {
          return this.count === 0;
        }
        size() {
          return this.count;
        }
        // 扩容
        reSize(newLimit) {
          let oldStorage = this.storage;
          this.storage = [];
          this.count = 0;
          this.limit = HashTable.getPrime(newLimit);
          for (let i = 0; i < oldStorage.length; i++) {
            let bucket = oldStorage[i];
            if (bucket == null) {
              continue;
            }
            for (let j = 0; j < bucket.length; j++) {
              let tuple = bucket[j];
              this.put(tuple[0], tuple[1]);
            }
          }
        }
        // 判断是否为质数
        static isPrime(num) {
          let temp = parseInt(Math.sqrt(num));
          for (let i = 2; i <= temp; i++) {
            if (num % i == 0) return false;
          }
          return true;
        }
        static getPrime(num) {
          while (!HashTable.isPrime(num)) {
            num += 1;
          }
          console.log(num)
          return num;
        }
      }

      let hash = new HashTable(4);
      hash.put("abc", "123");
      hash.put("def", "456");
      hash.put("egh", "789");
      // hash.remove("egh");
      // hash.remove("def");
      console.log(hash);
    </script>
  </body>
</html>
